<html>
<head>
	<meta charset="UTF-8">
	<meta content="IE=edge" http-equiv="X-UA-Compatible">
	<meta content="initial-scale=1.0, maximum-scale=1.0, user-scalable=no, width=device-width" name="viewport">
	<title>3843：ZCC loves Army</title>
	<!-- css -->
	<link href="../css/base.min.css" rel="stylesheet">
	<link href="../css/project.min.css" rel="stylesheet">
	
	<!-- favicon -->
	<!-- ... -->
</head>
<body class="page-brand">
	<header class="header header-transparent header-waterfall ui-header">
		<ul class="nav nav-list pull-left">
			<li>
				<a data-toggle="menu" href="#menu">
					<span class="icon icon-lg">menu</span>
				</a>
			</li>
		</ul>
		<a class="header-logo header-affix-hide margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">ZCC loves Army</a>
		<span class="header-logo header-affix margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">ZCC loves Army</span>
	</header>
	<nav aria-hidden="true" class="menu" id="menu" tabindex="-1">
		<div class="menu-scroll">
			<div class="menu-content">
				<a class="menu-logo" href="../index.html">BZOJ离线题库</a>
				<ul class="nav">
					<li>
						<a class="waves-attach" data-toggle="collapse" href="#problems">题目</a>
						<ul class="menu-collapse collapse in" id="problems">
							<li>
								<a class="waves-attach" href="../index.html">主页</a>
							</li>
							<li>
								<a class="waves-attach" href="../list.html">题目列表</a>
							</li>
						</ul>
					</li>
					<li>
						<a class="collapsed waves-attach" data-toggle="collapse" href="#about">关于</a>
						<ul class="menu-collapse collapse" id="about">
							<li>
								<a class="waves-attach" href="../about.html">关于此项目</a>
							</li>
						</ul>
					</li>
					
				</ul>
			</div>
		</div>
	</nav>
	<main class="content">
		<div class="content-header ui-content-header">
			<div class="container">
				<h1 class="content-heading">
                ZCC loves Army                </h1>
                <p>时间限制：2s&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;  空间限制：64MB</p>			</div>
		</div>
		<div class="container">
			<section class="content-inner margin-top-no">
				<div class="row">
					<div class="col-lg-13 col-md-13">
						<div class="card margin-bottom-no">
							<div class="card-main">
								<div class="card-inner">
									
                                <h3>题目描述</h3><p><div>ZCC owns an army with n soldiers. Soldiers are numbered from 1 to n. Soldier 1 is the commander in chief. Each soldier has a direct superior (which is called father in ACM) except soldier 1. x is a direct inferior (which is called son in ACM) of y if and only if y is the direct superior of x. Soldier use an ordered list called direct inferiors list to manage his direct inferiors (The indexes begin with 1). If soldier A and soldier B are in the same direct inferiors list, and A is in front of B, then we say A&rsquo;s level is higher than B. We assume that soldier 1 belongs to a direct inferior list that only contains soldier 1 for convenience.</div>
<div>Messages can be transmitted among the soldiers. A soldier can directly send messages to his direct superior, his direct inferior, and those who are in the same direct inferior list with him. Messages can also be sent indirectly. That means if x wants to send a message to y, he first send it directly to a third soldier z, then z send this message directly to y. In this case, we say z is involved in this transmission as a middleman. Message transmission that involves more than one middleman is also allowed.</div>
<div>Orders can be transmitted among the soldiers too. A soldier can directly give orders to his direct inferior and those who are in the same direct inferior list with him but have lower level. Orders can also be given indirectly. That means if x wants to give an order to y, he first give it to a third soldier z, then z give this order to y. In this case, we say z is involved in this transmission as a middleman. Order transmission that involves more than one middleman is also allowed.</div>
<div>Unfortunately, sometimes some soldiers will change their direct superior. More specifically, event like &ldquo;the p-th soldier to (p+c-1)-th soldier in soldier x&rsquo;s direct inferior list change their direct superior to y and be inserted after the q-th soldier in y&rsquo;s direct inferior list (if q=0, that means these soldiers are inserted in front of the first soldier in y&rsquo;s direct inferior list)&rdquo; will sometimes happen.</div>
<div>To examine the efficiency of the transmission of the messages and orders, ZCC will ask two types of question:&nbsp;</div>
<div>1) If soldier x want to send messages to soldier y, at least how many soldiers will be involved in this transmission as a middleman.</div>
<div>2) How many soldiers can give orders to soldier x.</div>
<div>Now, m events, including direct superior change events and ZCC&rsquo;s questions, happen one by one. Can you answer all ZCC&rsquo;s questions?</div>
<div></div>
<div></div>
<p></p></p><hr/><h3>输入格式</h3><p><div>
<div>The first line contains two integers n and m, indicating the number of soldiers and the number of events.</div>
<div>Then n lines follow, describing the initial direct inferior list of each soldier. The i-th line contains several integers. The first integer is k, indicating the number of soldier i&rsquo;s direct inferior. Then k integers follow, indicating the direct inferior list of soldier i.</div>
<div>After that m lines follow, describing the m events. Each line begins with an integer t, indicating the type of this event.</div>
<div>If t = 1, then 5 integers x, p, c, y and q follow, indicating a direct superior change event;</div>
<div>If t = 2, then 2 integers x and y follow, indicating ZCC&rsquo;s question 1;</div>
<div>If t = 3, then an integer x follows, indicating ZCC&rsquo;s question 2.</div>
<div></div>
</div>
<p></p></p><hr/><h3>输出格式</h3><p><div>For each question, output one line with one integer indicating your answer.</div>
<div></div>
<p></p></p><hr/><h3>样例输入</h3><pre>9 7
2 2 3
3 4 5 6
3 7 8 9
0
0
0
0
0
0
3 1
3 9
1 2 2 2 3 2
3 9
2 5 9
2 4 8
3 3</pre><hr/><h3>样例输出</h3><pre>0
5
7
0
2
2</pre><hr/><h3>提示</h3><p><div>&nbsp;n&lt;=100000, m&lt;=100000</div>
<div>&nbsp;You can assume that the events are all legal, and the relationship among the soldiers forms a tree all the time.</div>
<p></p></p><hr/><h3>题目来源</h3><p>By 镇海中学</p>
								</div>
							</div>
						</div>
					</div>
				</div>
				
				
			</section>
		</div>
	</main>

	<div class="fbtn-container">
		<div class="fbtn-inner">
			<a class="fbtn fbtn-lg fbtn-brand-accent waves-attach waves-circle waves-light waves-effect" data-toggle="dropdown" aria-expanded="true"><span class="fbtn-text fbtn-text-left">Menu</span><span class="fbtn-ori icon">apps</span><span class="fbtn-sub icon">close</span></a>
			<div class="fbtn-dropup">
				<a class="fbtn fbtn-brand waves-attach waves-circle waves-light waves-effect" href="../list.html" target="_self"><span class="fbtn-text fbtn-text-left">题目列表</span><span class="icon">menu</span></a>
				<a class="fbtn fbtn-green waves-attach waves-circle waves-effect" href="../index.html" target="_self"><span class="fbtn-text fbtn-text-left">返回主页</span><span class="icon">home</span></a>
				<a class="fbtn waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/submitpage.php?id=3843" target="_blank"><span class="fbtn-text fbtn-text-left">提交代码</span><span class="icon">send</span></a>
				<a class="fbtn fbtn-orange waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/wttl/wttl.php?pid=3843" target="_blank"><span class="fbtn-text fbtn-text-left">试题讨论</span><span class="icon">chat</span></a>
				
			</div>
		</div>
	</div>

	<!-- js -->
	<script src="../js/jquery.min.js"></script>
	<script src="../js/base.min.js"></script>
	<script src="../js/project.min.js"></script>
</body>
</html>